package com.cjm.algorithm.leetcode;

public class ClimbingStairs70 {
    private static int m1(int n) {
        // 2 -> {1,1} {2}
        // 1 -> {1}
        // 3 -> {1, 1, 1}, {1, 2}, {2, 1}
        // 4 -> {1, 1, 1, 1} {1, 1, 2} {1, 2, 1}, {2, 1, 1}, {2, 2}
        // f(n) = f(n - 1) + f(n - 2)
        if (n == 0) {
            return 1;
        }

        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int x = 1;
        int y = 2;
        for (int i = 3; i <= n; i++) {
            int temp = (x + y)%(1000000007);
            x = y;
            y = temp;
        }
        return y;
    }

    public static void main(String[] args) {
        System.err.println(m1(44));
    }
}
